<!DOCTYPE html>
<html lang="zh-CN">
<!--浏览器搞笑标题-->
<script type="text/javascript" src="/js/FunnyTitle.js"></script>






<head>
  <meta charset="UTF-8">
  <link rel="apple-touch-icon" sizes="76x76" href="/binblog/img/binblog.ico">
  <link rel="icon" type="image/png" href="/binblog/img/binblog.ico">
  <meta name="viewport"
        content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=no, shrink-to-fit=no">
  <meta http-equiv="x-ua-compatible" content="ie=edge">
  
  <meta name="theme-color" content="#2f4154">
  <meta name="description" content="">
  <meta name="author" content="leo-bin">
  <meta name="keywords" content="">
  <title>纯手写LRU算法！ - 阿斌的个人博客</title>

  <link  rel="stylesheet" href="https://cdn.staticfile.org/twitter-bootstrap/4.4.1/css/bootstrap.min.css" />


  <link  rel="stylesheet" href="https://cdn.staticfile.org/github-markdown-css/4.0.0/github-markdown.min.css" />
  <link  rel="stylesheet" href="/binblog/lib/hint/hint.min.css" />

  
    <link  rel="stylesheet" href="https://cdn.staticfile.org/highlight.js/10.0.0/styles/dracula.min.css" />
  

  


<!-- 主题依赖的图标库，不要自行修改 -->

<link rel="stylesheet" href="//at.alicdn.com/t/font_1749284_yg9cfy8wd6.css">



<link rel="stylesheet" href="//at.alicdn.com/t/font_1736178_pjno9b9zyxs.css">


<link  rel="stylesheet" href="/binblog/css/main.css" />

<!-- 自定义样式保持在最底部 -->


<meta name="generator" content="Hexo 4.2.1"></head>


<body>
  <header style="height: 70vh;">
    <nav id="navbar" class="navbar fixed-top  navbar-expand-lg navbar-dark scrolling-navbar">
  <div class="container">
    <a class="navbar-brand"
       href="/binblog/">&nbsp;<strong>Abin的Blog</strong>&nbsp;</a>

    <button id="navbar-toggler-btn" class="navbar-toggler" type="button" data-toggle="collapse"
            data-target="#navbarSupportedContent"
            aria-controls="navbarSupportedContent" aria-expanded="false" aria-label="Toggle navigation">
      <div class="animated-icon"><span></span><span></span><span></span></div>
    </button>

    <!-- Collapsible content -->
    <div class="collapse navbar-collapse" id="navbarSupportedContent">
      <ul class="navbar-nav ml-auto text-center">
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/binblog/">
                <i class="iconfont icon-home-fill"></i>
                首页
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/binblog/archives/">
                <i class="iconfont icon-archive-fill"></i>
                归档
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/binblog/categories/">
                <i class="iconfont icon-category-fill"></i>
                分类
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/binblog/tags/">
                <i class="iconfont icon-tags-fill"></i>
                标签
              </a>
            </li>
          
        
          
          
          
          
            <li class="nav-item">
              <a class="nav-link" href="/binblog/about/">
                <i class="iconfont icon-user-fill"></i>
                关于
              </a>
            </li>
          
        
        
          <li class="nav-item" id="search-btn">
            <a class="nav-link" data-toggle="modal" data-target="#modalSearch">&nbsp;&nbsp;<i
                class="iconfont icon-search"></i>&nbsp;&nbsp;</a>
          </li>
        
      </ul>
    </div>
  </div>
</nav>

    <div class="view intro-2" id="background" parallax=true
         style="background: url('/binblog/img/6.webp') no-repeat center center;
           background-size: cover;">
      <div class="full-bg-img">
        <div class="mask flex-center" style="background-color: rgba(0, 0, 0, 0.3)">
          <div class="container text-center white-text fadeInUp">
            <span class="h2" id="subtitle">
              
            </span>

            
              
  <div class="mt-3 post-meta">
    <i class="iconfont icon-date-fill" aria-hidden="true"></i>
    <time datetime="2020-05-31 00:41">
      2020年5月31日 凌晨
    </time>
  </div>


<div class="mt-1">
  
    
    <span class="post-meta mr-2">
      <i class="iconfont icon-chart"></i>
      1.6k 字
    </span>
  

  
    
    <span class="post-meta mr-2">
      <i class="iconfont icon-clock-fill"></i>
      
      
      22
       分钟
    </span>
  

  
  
    
      <!-- LeanCloud 统计文章PV -->
      <span id="leancloud-post-views-container" class="post-meta" style="display: none">
        <i class="iconfont icon-eye" aria-hidden="true"></i>
        <span id="leancloud-post-views"></span> 次
      </span>
    
  
</div>

            
          </div>

          
        </div>
      </div>
    </div>
  </header>

  <main>
    
      

<div class="container-fluid">
  <div class="row">
    <div class="d-none d-lg-block col-lg-2"></div>
    <div class="col-lg-8 nopadding-md">
      <div class="container nopadding-md" id="board-ctn">
        <div class="py-5" id="board">
          <div class="post-content mx-auto" id="post">
            
              <p class="note note-info">
                
                  本文最后更新于：2020年5月31日 凌晨
                
              </p>
            
            <article class="markdown-body">
              <h1 id="纯手写LRU算法！"><a href="#纯手写LRU算法！" class="headerlink" title="纯手写LRU算法！"></a>纯手写LRU算法！</h1><h2 id="什么是LRU？"><a href="#什么是LRU？" class="headerlink" title="什么是LRU？"></a>什么是LRU？</h2><p><strong>1.Latest Recently Unuesd（最近最少未使用）。</strong></p>
<p><strong>2.如果一个数据在最近一段时间内都没有被访问，那么就认为这个数据在以后被访问的概率也很小了。</strong></p>
<p><strong>3.所以当内存满了的时候，这个数据就会最先被淘汰掉。</strong></p>
<h2 id="如何实现？"><a href="#如何实现？" class="headerlink" title="如何实现？"></a>如何实现？</h2><p><strong>1.最朴素的思想就是用数组+时间戳的方式，不过这样做效率较低。</strong></p>
<p><strong>2.因此，我们可以用双向链表+哈希表（HashMap）实现（链表用来表示位置，哈希表用来存储和查找）。</strong></p>
<p><strong>3或者也可以利用Java中现成的数据结构LinkedHashMap来实现一个简单的LRU算法。</strong></p>
<h2 id="一-使用现有的数据结构实现"><a href="#一-使用现有的数据结构实现" class="headerlink" title="一  使用现有的数据结构实现"></a>一  使用现有的数据结构实现</h2><h3 id="使用LinkedHashMap实现"><a href="#使用LinkedHashMap实现" class="headerlink" title="使用LinkedHashMap实现"></a><strong>使用LinkedHashMap实现</strong></h3><div class="hljs"><pre><code class="hljs java"><span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">LRUCache</span>&lt;<span class="hljs-title">K</span>, <span class="hljs-title">V</span>&gt; <span class="hljs-keyword">extends</span> <span class="hljs-title">LinkedHashMap</span>&lt;<span class="hljs-title">K</span>, <span class="hljs-title">V</span>&gt; </span>&#123;
    <span class="hljs-comment">/**</span>
<span class="hljs-comment">     * 初始缓存大小</span>
<span class="hljs-comment">     */</span>
    <span class="hljs-keyword">private</span> <span class="hljs-keyword">final</span> <span class="hljs-keyword">int</span> CACHE_SIZE;
    <span class="hljs-comment">/**</span>
<span class="hljs-comment">     * 初始化缓存，并设置大小</span>
<span class="hljs-comment">     *</span>
<span class="hljs-comment">     * <span class="hljs-doctag">@param</span> cacheSize 缓存大小</span>
<span class="hljs-comment">     */</span>
    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">LRUCache</span><span class="hljs-params">(<span class="hljs-keyword">int</span> cacheSize)</span> </span>&#123;
        <span class="hljs-comment">//初始化一个LinkedHashMap，true表示按照访问顺序来进行排序，最近访问的数据放在尾部，最老访问的放在头部</span>
        <span class="hljs-keyword">super</span>((<span class="hljs-keyword">int</span>) Math.ceil((cacheSize / <span class="hljs-number">0.75</span>) + <span class="hljs-number">1</span>), <span class="hljs-number">0.75f</span>, <span class="hljs-keyword">true</span>);
        <span class="hljs-keyword">this</span>.CACHE_SIZE = cacheSize;
    &#125;

    <span class="hljs-comment">/**</span>
<span class="hljs-comment">     * 是否移除最久没被访问的那个节点</span>
<span class="hljs-comment">     *</span>
<span class="hljs-comment">     * <span class="hljs-doctag">@return</span> 是否满足删除条件</span>
<span class="hljs-comment">     */</span>
    <span class="hljs-meta">@Override</span>
    <span class="hljs-function"><span class="hljs-keyword">protected</span> <span class="hljs-keyword">boolean</span> <span class="hljs-title">removeEldestEntry</span><span class="hljs-params">(Map.Entry&lt;K, V&gt; eldest)</span> </span>&#123;
        <span class="hljs-comment">//判断现在map中的数量是否达到了指定的缓存数</span>
        <span class="hljs-comment">//在调用put方法的时候，会调用这个方法，如果达到了缓存的大小，删掉最长时间没被访问的entry</span>
        <span class="hljs-keyword">return</span> size() &gt; CACHE_SIZE;
    &#125;
&#125;</code></pre></div>
<h3 id="测试代码："><a href="#测试代码：" class="headerlink" title="测试代码："></a><strong>测试代码：</strong></h3><div class="hljs"><pre><code class="hljs java"><span class="hljs-keyword">import</span> org.slf4j.Logger;
<span class="hljs-keyword">import</span> org.slf4j.LoggerFactory;

<span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">LRUTest</span> </span>&#123;
    <span class="hljs-keyword">private</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">final</span> Logger log = LoggerFactory.getLogger(LRUTest<span class="hljs-class">.<span class="hljs-keyword">class</span>)</span>;

    <span class="hljs-comment">/**</span>
<span class="hljs-comment">     * 初始化一个容量大小为10的LRU缓存</span>
<span class="hljs-comment">     */</span>
    <span class="hljs-keyword">private</span> <span class="hljs-keyword">static</span> LRUCache&lt;String, Integer&gt; lruCache = <span class="hljs-keyword">new</span> LRUCache&lt;&gt;(<span class="hljs-number">10</span>);


    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">main</span><span class="hljs-params">(String[] args)</span> </span>&#123;
        <span class="hljs-comment">//往缓存中加10个数，加入之后，缓存现在已经满了</span>
        <span class="hljs-keyword">for</span> (<span class="hljs-keyword">int</span> i = <span class="hljs-number">0</span>; i &lt; <span class="hljs-number">8</span>; i++) &#123;
            lruCache.put(<span class="hljs-string">"k"</span> + i, i);
        &#125;
        <span class="hljs-comment">//先看看现在缓存中的情况</span>
        log.info(<span class="hljs-string">"all cache:&#123;&#125;"</span>, lruCache);

        <span class="hljs-comment">//先访问一次k3</span>
        lruCache.get(<span class="hljs-string">"k3"</span>);
        log.info(<span class="hljs-string">"get k3之后：&#123;&#125;"</span>, lruCache);

        <span class="hljs-comment">//在访问一次k4</span>
        lruCache.get(<span class="hljs-string">"k4"</span>);
        log.info(<span class="hljs-string">"get k4之后：&#123;&#125;"</span>, lruCache);

        <span class="hljs-comment">//往容量已经满了的缓存中再加一个数k10,看看谁被淘汰了</span>
        lruCache.put(<span class="hljs-string">"k10"</span>, <span class="hljs-number">10</span>);
        log.info(<span class="hljs-string">"put k10之后：&#123;&#125;"</span>, lruCache);
    &#125;
&#125;</code></pre></div>
<h3 id="测试结果："><a href="#测试结果：" class="headerlink" title="测试结果："></a><strong>测试结果：</strong></h3><p><img src="https://s1.ax1x.com/2020/05/02/JxCWY4.jpg" srcset="/binblog/img/loading.gif" alt="JxCWY4.jpg"></p>
<h2 id="二-使用HashMap-双向链表实现"><a href="#二-使用HashMap-双向链表实现" class="headerlink" title="二  使用HashMap+双向链表实现"></a>二  使用HashMap+双向链表实现</h2><p><strong>1.其实我们也可以利用双向链表的特点，分别设置一个头指针和尾指针，从而方便的进行双向遍历。</strong></p>
<p><strong>2.要想实现put和get操作都是O(1)的时间复杂度我们使用HashMap来存储我们的双向链表的节点。</strong></p>
<p><strong>3.put操作需要做两件事情，一是检查缓存空间是否达到预期阈值，如果没满，直接存map然后修改双向链表的指向。</strong></p>
<p><strong>4.二是如果要put的元素已经存在过了，那么这次put就相当于update，我们需要更新下该元素的访问频率。</strong></p>
<p><strong>5.访问频率本质上就是先在双向链表中将该元素删掉，然后重新添加到链表尾部。</strong></p>
<p><strong>6.如果put时达到了阈值，那就需要做淘汰，根据LRU的特性应该将最近最少使用过的元素淘汰掉，我们直接将链表头的元素删掉然后重新调正双向链表就行。</strong></p>
<h3 id="代码如下："><a href="#代码如下：" class="headerlink" title="代码如下："></a>代码如下：</h3><div class="hljs"><pre><code class="hljs java"><span class="hljs-comment">/**</span>
<span class="hljs-comment"> * <span class="hljs-doctag">@author</span> leo-bin</span>
<span class="hljs-comment"> * <span class="hljs-doctag">@date</span> 2020/4/7 19:44</span>
<span class="hljs-comment"> * <span class="hljs-doctag">@apiNote</span> 使用HashMap+双链表+synchronized实现(线程安全)</span>
<span class="hljs-comment"> */</span>
<span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">LRUCacheV2</span> </span>&#123;
    <span class="hljs-comment">/**</span>
<span class="hljs-comment">     * 缓存容量</span>
<span class="hljs-comment">     */</span>
    <span class="hljs-keyword">private</span> <span class="hljs-keyword">final</span> <span class="hljs-keyword">int</span> cacheSize;
    <span class="hljs-keyword">private</span> HashMap&lt;String, Node&gt; map;
    <span class="hljs-keyword">private</span> Node head;
    <span class="hljs-keyword">private</span> Node tail;

    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">LRUCacheV2</span><span class="hljs-params">(<span class="hljs-keyword">int</span> cacheSize)</span> </span>&#123;
        <span class="hljs-keyword">this</span>.cacheSize = cacheSize;
        <span class="hljs-keyword">this</span>.map = <span class="hljs-keyword">new</span> HashMap&lt;&gt;(<span class="hljs-number">16</span>);
    &#125;

    <span class="hljs-comment">/**</span>
<span class="hljs-comment">     * 内部节点类</span>
<span class="hljs-comment">     */</span>
    <span class="hljs-keyword">public</span> <span class="hljs-class"><span class="hljs-keyword">class</span> <span class="hljs-title">Node</span> </span>&#123;
        <span class="hljs-keyword">private</span> String key;
        <span class="hljs-keyword">private</span> <span class="hljs-keyword">volatile</span> String value;
        <span class="hljs-keyword">private</span> Node pre;
        <span class="hljs-keyword">private</span> Node next;

        <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-title">Node</span><span class="hljs-params">(String key, String value)</span> </span>&#123;
            <span class="hljs-keyword">this</span>.key = key;
            <span class="hljs-keyword">this</span>.value = value;
        &#125;
    &#125;

    <span class="hljs-comment">/**</span>
<span class="hljs-comment">     * get操作</span>
<span class="hljs-comment">     * 时间复杂度：O(1)</span>
<span class="hljs-comment">     */</span>
    <span class="hljs-function"><span class="hljs-keyword">public</span> String <span class="hljs-title">get</span><span class="hljs-params">(String key)</span> </span>&#123;
        Node node = map.get(key);
        <span class="hljs-keyword">if</span> (node == <span class="hljs-keyword">null</span>) &#123;
            <span class="hljs-keyword">return</span> <span class="hljs-keyword">null</span>;
        &#125; <span class="hljs-keyword">else</span> &#123;
            refreshNode(node);
            <span class="hljs-keyword">return</span> node.value;
        &#125;
    &#125;

    <span class="hljs-comment">/**</span>
<span class="hljs-comment">     * put操作</span>
<span class="hljs-comment">     * 时间复杂度：O(1)</span>
<span class="hljs-comment">     */</span>
    <span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">void</span> <span class="hljs-title">put</span><span class="hljs-params">(String key, String value)</span> </span>&#123;
        Node node = map.get(key);
        <span class="hljs-keyword">synchronized</span> (<span class="hljs-keyword">this</span>) &#123;
            <span class="hljs-keyword">if</span> (node == <span class="hljs-keyword">null</span>) &#123;
                <span class="hljs-comment">//缓存已满，需要删除最近最少使用的节点，其实就是头结点</span>
                <span class="hljs-keyword">if</span> (map.size() &gt;= cacheSize) &#123;
                    Node oldNode = removeNode(head);
                    map.remove(oldNode.key);
                &#125;
                <span class="hljs-comment">//没满或者删掉之后，放map中</span>
                node = <span class="hljs-keyword">new</span> Node(key, value);
                map.put(key, node);
                addNode(node);
            &#125;
            <span class="hljs-comment">//node已经存在，修改访问频率，并修改map中的value</span>
            <span class="hljs-keyword">else</span> &#123;
                node.value = value;
                map.put(key, node);
                refreshNode(node);
            &#125;
        &#125;
    &#125;

    <span class="hljs-comment">/**</span>
<span class="hljs-comment">     * 刷新当前的链表</span>
<span class="hljs-comment">     */</span>
    <span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">void</span> <span class="hljs-title">refreshNode</span><span class="hljs-params">(Node node)</span> </span>&#123;
        <span class="hljs-keyword">if</span> (node == tail) &#123;
            <span class="hljs-keyword">return</span>;
        &#125;
        <span class="hljs-keyword">if</span> (node != <span class="hljs-keyword">null</span>) &#123;
            removeNode(node);
            addNode(node);
        &#125;
    &#125;

    <span class="hljs-comment">/**</span>
<span class="hljs-comment">     * 往链表尾部增加一个节点</span>
<span class="hljs-comment">     */</span>
    <span class="hljs-function"><span class="hljs-keyword">private</span> <span class="hljs-keyword">void</span> <span class="hljs-title">addNode</span><span class="hljs-params">(Node node)</span> </span>&#123;
        <span class="hljs-comment">//1.head为空，那就将head指向node</span>
        <span class="hljs-keyword">if</span> (head == <span class="hljs-keyword">null</span>) &#123;
            head = node;
        &#125;
        <span class="hljs-comment">//2.tail不为空说明链表中有元素了，改变指向</span>
        <span class="hljs-keyword">if</span> (tail != <span class="hljs-keyword">null</span>) &#123;
            tail.next = node;
            node.pre = tail;
            node.next = <span class="hljs-keyword">null</span>;
        &#125;
        <span class="hljs-comment">//3.tail无论如何都要先指向node</span>
        tail = node;
    &#125;

    <span class="hljs-comment">/**</span>
<span class="hljs-comment">     * 随机删除链表中的一个节点</span>
<span class="hljs-comment">     */</span>
    <span class="hljs-function"><span class="hljs-keyword">private</span> Node <span class="hljs-title">removeNode</span><span class="hljs-params">(Node node)</span> </span>&#123;
        <span class="hljs-comment">//鲁棒</span>
        <span class="hljs-keyword">if</span> (node == <span class="hljs-keyword">null</span>) &#123;
            <span class="hljs-keyword">return</span> node;
        &#125;
        <span class="hljs-comment">//1.要删除的节点是唯一节点</span>
        <span class="hljs-keyword">if</span> (node == head &amp;&amp; node == tail) &#123;
            head = <span class="hljs-keyword">null</span>;
            tail = <span class="hljs-keyword">null</span>;
        &#125;
        <span class="hljs-comment">//2.要删除的节点是head节点</span>
        <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (node == head) &#123;
            head = node.next;
            node.next.pre = <span class="hljs-keyword">null</span>;
            node.next = <span class="hljs-keyword">null</span>;
        &#125;
        <span class="hljs-comment">//3.要删除的节点是tail节点</span>
        <span class="hljs-keyword">else</span> <span class="hljs-keyword">if</span> (node == tail) &#123;
            tail = node.pre;
            node.pre.next = <span class="hljs-keyword">null</span>;
            node.pre = <span class="hljs-keyword">null</span>;
        &#125;
        <span class="hljs-comment">//4.要删除的节点是中间节点</span>
        <span class="hljs-keyword">else</span> &#123;
            node.pre.next = node.next;
            node.next.pre = node.pre;
            node.next = <span class="hljs-keyword">null</span>;
            node.pre = <span class="hljs-keyword">null</span>;
        &#125;
        <span class="hljs-keyword">return</span> node;
    &#125;</code></pre></div>
<h3 id="测试代码：-1"><a href="#测试代码：-1" class="headerlink" title="测试代码："></a><strong>测试代码：</strong></h3><div class="hljs"><pre><code class="hljs java"><span class="hljs-function"><span class="hljs-keyword">public</span> <span class="hljs-keyword">static</span> <span class="hljs-keyword">void</span> <span class="hljs-title">main</span><span class="hljs-params">(String[] args)</span> </span>&#123;
    LRUCacheV2 lruCache = <span class="hljs-keyword">new</span> LRUCacheV2(<span class="hljs-number">4</span>);
    <span class="hljs-comment">//初始化缓存，加四个元素进去</span>
    lruCache.put(<span class="hljs-string">"1"</span>, <span class="hljs-string">"User1"</span>);
    lruCache.put(<span class="hljs-string">"2"</span>, <span class="hljs-string">"User2"</span>);
    lruCache.put(<span class="hljs-string">"3"</span>, <span class="hljs-string">"User3"</span>);
    lruCache.put(<span class="hljs-string">"4"</span>, <span class="hljs-string">"User4"</span>);

    <span class="hljs-comment">//get一下其中一个元素User1</span>
    System.out.println(lruCache.get(<span class="hljs-string">"1"</span>));

    <span class="hljs-comment">//再加一个元素，加入之后User2应该被删掉了</span>
    lruCache.put(<span class="hljs-string">"5"</span>, <span class="hljs-string">"User5"</span>);

    <span class="hljs-comment">//验证下User2是否被删掉了</span>
    System.out.println(<span class="hljs-string">"User2="</span> + lruCache.get(<span class="hljs-string">"2"</span>));
&#125;</code></pre></div>
<h3 id="测试结果：-1"><a href="#测试结果：-1" class="headerlink" title="测试结果："></a><strong>测试结果：</strong></h3><p><img src="https://s1.ax1x.com/2020/05/02/JxPVpj.jpg" srcset="/binblog/img/loading.gif" alt="JxPVpj.jpg"></p>
<h2 id="总结"><a href="#总结" class="headerlink" title="总结"></a>总结</h2><p><strong>1.lru算法早在我们学习操作系统这门课程的时候就已经略有耳闻了。</strong></p>
<p><strong>2.当时懒呀！总是不去学习这种底层算法和数据结构，因为我觉得这么复杂的算法以后不会碰到。</strong></p>
<p><strong>3.但是！我就是太年轻！</strong></p>
<p><strong>4.本人在今年春招时腾讯一面中就碰到了要手写LRU算法，并且还要实现O（1）的时间复杂度！</strong></p>
<p><strong>5.经过这一次的失利，吃一堑长一智，加油！</strong></p>
<h2 id="链接"><a href="#链接" class="headerlink" title="链接"></a>链接</h2><p><strong>这里提供给大家一个练习LRU算法的地方，没错！就是leetcode！</strong></p>
<p><strong>传送门：    <a href="https://leetcode-cn.com/problems/lru-cache/" target="_blank" rel="noopener">https://leetcode-cn.com/problems/lru-cache/</a></strong></p>

            </article>
            <hr>
            <div>
              <div class="post-metas mb-3">
                
                  <div class="post-meta mr-3">
                    <i class="iconfont icon-category"></i>
                    
                      <a class="hover-with-bg" href="/binblog/categories/%E7%AE%97%E6%B3%95/">算法</a>
                    
                  </div>
                
                
              </div>
              
                <p class="note note-warning">本博客所有文章除特别声明外，均采用 <a href="https://creativecommons.org/licenses/by-sa/4.0/deed.zh" target="_blank" rel="nofollow noopener noopener">CC BY-SA 4.0 协议</a> ，转载请注明出处！</p>
              
              
                <div class="post-prevnext row">
                  <div class="post-prev col-6">
                    
                    
                      <a href="/binblog/2020/05/31/%E8%AE%BE%E8%AE%A1%E6%A8%A1%E5%BC%8F%E4%B9%8B%E4%BB%A3%E7%90%86%E6%A8%A1%E5%BC%8F/">
                        <i class="iconfont icon-arrowleft"></i>
                        <span class="hidden-mobile">设计模式之代理模式</span>
                        <span class="visible-mobile">上一篇</span>
                      </a>
                    
                  </div>
                  <div class="post-next col-6">
                    
                    
                      <a href="/binblog/2020/05/31/%E5%88%86%E5%B8%83%E5%BC%8F%E5%9C%BA%E6%99%AF%E4%B8%8B%E7%9A%84%E5%85%A8%E5%B1%80%E5%94%AF%E4%B8%80id%E7%94%9F%E6%88%90%E6%96%B9%E6%A1%88/">
                        <span class="hidden-mobile">分布式场景下的全局唯一id生成方案</span>
                        <span class="visible-mobile">下一篇</span>
                        <i class="iconfont icon-arrowright"></i>
                      </a>
                    
                  </div>
                </div>
              
            </div>

            
              <!-- Comments -->
              <div class="comments" id="comments">
                
                
  <div id="vcomments"></div>
  <script defer src="https://cdn.staticfile.org/valine/1.4.14/Valine.min.js" ></script>

  <script type="text/javascript">
    var oldLoadVa = window.onload;
    window.onload = function () {
      oldLoadVa && oldLoadVa();

      new Valine({
        el: "#vcomments",
        app_id: "vsanVmkaurLHyq2Xey9odo5V-gzGzoHsz",
        app_key: "v2hMMe4Mzz3mqpy9jwd7qx8B",
        placeholder: "说点什么吧！",
        path: window.location.pathname,
        avatar: "retro",
        meta: ["nick","mail","link"],
        pageSize: "10",
        lang: "zh-CN",
        highlight: true,
        recordIP: false,
        serverURLs: "",
      });
    };
  </script>
  <noscript>Please enable JavaScript to view the <a href="https://valine.js.org" target="_blank" rel="nofollow noopener noopener">comments
      powered by Valine.</a></noscript>


              </div>
            
          </div>
        </div>
      </div>
    </div>
    
      <div class="d-none d-lg-block col-lg-2 toc-container" id="toc-ctn">
        <div id="toc">
  <p class="toc-header"><i class="iconfont icon-list"></i>&nbsp;目录</p>
  <div id="tocbot"></div>
</div>

      </div>
    
  </div>
</div>

<!-- Custom -->


    
  </main>

  
    <a id="scroll-top-button" href="#" role="button">
      <i class="iconfont icon-arrowup" aria-hidden="true"></i>
    </a>
  

  
    <div class="modal fade" id="modalSearch" tabindex="-1" role="dialog" aria-labelledby="ModalLabel"
     aria-hidden="true">
  <div class="modal-dialog modal-dialog-scrollable modal-lg" role="document">
    <div class="modal-content">
      <div class="modal-header text-center">
        <h4 class="modal-title w-100 font-weight-bold">搜索</h4>
        <button type="button" id="local-search-close" class="close" data-dismiss="modal" aria-label="Close">
          <span aria-hidden="true">&times;</span>
        </button>
      </div>
      <div class="modal-body mx-3">
        <div class="md-form mb-5">
          <input type="text" id="local-search-input" class="form-control validate">
          <label data-error="x" data-success="v"
                 for="local-search-input">关键词</label>
        </div>
        <div class="list-group" id="local-search-result"></div>
      </div>
    </div>
  </div>
</div>
  

  

  

  <footer class="mt-5">
  <div class="text-center py-3">
    <div>
      <a href="https://hexo.io" target="_blank" rel="nofollow noopener"><span>Hexo</span></a>
      <i class="iconfont icon-love"></i>
      <a href="https://github.com/fluid-dev/hexo-theme-fluid" target="_blank" rel="nofollow noopener">
        <span>Fluid</span></a>
    </div>
    
  <div class="statistics">
    
    

    
      
        <!-- LeanCloud 统计PV -->
        <span id="leancloud-site-pv-container" style="display: none">
            总访问量 
            <span id="leancloud-site-pv"></span>
             次
          </span>
      
      
        <!-- LeanCloud 统计UV -->
        <span id="leancloud-site-uv-container" style="display: none">
            总访客数 
            <span id="leancloud-site-uv"></span>
             人
          </span>
      

    
  </div>


    
  <!-- 备案信息 -->
  <div class="beian">
    <a href="http://beian.miit.gov.cn/" target="_blank"
       rel="nofollow noopener">京ICP证123456号</a>
    
      <a
        href="http://www.beian.gov.cn/portal/registerSystemInfo?recordcode=12345678"
        rel="nofollow noopener"
        class="beian-police"
        target="_blank"
      >
        <span class="beian-police-sep">&nbsp;|&nbsp;</span>
        
          <img src="/binblog/img/police_beian.png" srcset="/binblog/img/loading.gif" alt="police-icon" />
        
        <span>京公网安备12345678号</span>
      </a>
     
  </div>


    
  </div>
</footer>

<!-- SCRIPTS -->
<script  src="https://cdn.staticfile.org/jquery/3.4.1/jquery.min.js" ></script>
<script  src="https://cdn.staticfile.org/twitter-bootstrap/4.4.1/js/bootstrap.min.js" ></script>
<script  src="/binblog/js/debouncer.js" ></script>
<script  src="/binblog/js/main.js" ></script>

<!-- Plugins -->


  
    <script  src="/binblog/js/lazyload.js" ></script>
  



  <script defer src="https://cdn.staticfile.org/clipboard.js/2.0.6/clipboard.min.js" ></script>
  <script  src="/binblog/js/clipboard-use.js" ></script>



  <script defer>
  (function () {
    // 查询存储的记录
    function getRecord(Counter, target) {
      return new Promise(function (resolve, reject) {
        Counter('get', '/classes/Counter?where=' + encodeURIComponent(JSON.stringify({target})))
          .then(resp => resp.json())
          .then(({results, code, error}) => {
            if (code === 401) {
              throw error;
            }
            if (results && results.length > 0) {
              var record = results[0];
              resolve(record);
            } else {
              Counter('post', '/classes/Counter', {target, time: 0})
                .then(resp => resp.json())
                .then((record, error) => {
                  if (error) {
                    throw error;
                  }
                  resolve(record);
                }).catch(error => {
                console.error('Failed to create', error);
                reject(error);
              });
            }
          }).catch((error) => {
          console.error('LeanCloud Counter Error:', error);
          reject(error);
        });
      })
    }

    // 发起自增请求
    function increment(Counter, incrArr) {
      return new Promise(function (resolve, reject) {
        Counter('post', '/batch', {
          "requests": incrArr
        }).then((res) => {
          res = res.json();
          if (res.error) {
            throw res.error;
          }
          resolve(res);
        }).catch((error) => {
          console.error('Failed to save visitor count', error);
          reject(error);
        });
      });
    }

    // 构建自增请求体
    function buildIncrement(objectId) {
      return {
        "method": "PUT",
        "path": `/1.1/classes/Counter/${ objectId }`,
        "body": {
          "time": {
            '__op': 'Increment',
            'amount': 1
          }
        }
      }
    }

    // 校验是否为有效的 UV
    function validUV() {
      var key = 'LeanCloud_UV_Flag';
      var flag = localStorage.getItem(key);
      if (flag) {
        // 距离标记小于 24 小时则不计为 UV
        if (new Date().getTime() - parseInt(flag) <= 86400000) {
          return false;
        }
      }
      localStorage.setItem(key, new Date().getTime().toString());
      return true;
    }

    function addCount(Counter) {
      var enableIncr = 'true' === 'true' && window.location.hostname !== 'localhost';
      var getterArr = [];
      var incrArr = [];

      // 请求 PV 并自增
      var pvCtn = document.querySelector('#leancloud-site-pv-container');
      if (pvCtn || enableIncr) {
        var pvGetter = getRecord(Counter, 'site-pv').then((record) => {
          incrArr.push(buildIncrement(record.objectId))
          var ele = document.querySelector('#leancloud-site-pv');
          if (ele) {
            ele.innerText = record.time + 1;
            if (pvCtn) {
              pvCtn.style.display = 'inline';
            }
          }
        });
        getterArr.push(pvGetter);
      }

      // 请求 UV 并自增
      var uvCtn = document.querySelector('#leancloud-site-uv-container');
      if (uvCtn || enableIncr) {
        var uvGetter = getRecord(Counter, 'site-uv').then((record) => {
          var vuv = validUV();
          vuv && incrArr.push(buildIncrement(record.objectId))
          var ele = document.querySelector('#leancloud-site-uv');
          if (ele) {
            ele.innerText = record.time + (vuv ? 1 : 0);
            if (uvCtn) {
              uvCtn.style.display = 'inline';
            }
          }
        });
        getterArr.push(uvGetter);
      }

      // 如果是文章，请求文章的浏览数，并自增
      if ('true' === 'true') {
        var viewCtn = document.querySelector('#leancloud-post-views-container');
        if (viewCtn || enableIncr) {
          var target = decodeURI('/binblog/2020/05/31/%E7%BA%AF%E6%89%8B%E5%86%99LRU%E7%AE%97%E6%B3%95%EF%BC%81/');
          var viewGetter = getRecord(Counter, target).then((record) => {
            incrArr.push(buildIncrement(record.objectId))
            if (viewCtn) {
              var ele = document.querySelector('#leancloud-post-views');
              if (ele) {
                ele.innerText = (record.time || 0) + 1;
                viewCtn.style.display = 'inline';
              }
            }
          });
          getterArr.push(viewGetter);
        }
      }

      // 如果启动计数自增，批量发起自增请求
      if (enableIncr) {
        Promise.all(getterArr).then(() => {
          incrArr.length > 0 && increment(Counter, incrArr);
        })
      }
    }

    var app_id = 'vsanVmkaurLHyq2Xey9odo5V-gzGzoHsz'
    var app_key = 'v2hMMe4Mzz3mqpy9jwd7qx8B'
    var server_url = ''

    function fetchData(api_server) {
      var Counter = (method, url, data) => {
        return fetch(`${ api_server }/1.1${ url }`, {
          method,
          headers: {
            'X-LC-Id': app_id,
            'X-LC-Key': app_key,
            'Content-Type': 'application/json',
          },
          body: JSON.stringify(data)
        });
      };

      addCount(Counter);
    }

    var api_server = app_id.slice(-9) !== '-MdYXbMMI' ? server_url : `https://${ app_id.slice(0, 8).toLowerCase() }.api.lncldglobal.com`;

    if (api_server) {
      fetchData(api_server);
    } else {
      fetch('https://app-router.leancloud.cn/2/route?appId=' + app_id)
        .then(resp => resp.json())
        .then(({api_server}) => {
          fetchData('https://' + api_server);
        });
    }
  })();
</script>






  <script  src="https://cdn.staticfile.org/tocbot/4.11.1/tocbot.min.js" ></script>
  <script>
    $(document).ready(function () {
      var boardCtn = $('#board-ctn');
      var boardTop = boardCtn.offset().top;

      tocbot.init({
        tocSelector: '#tocbot',
        contentSelector: 'article.markdown-body',
        headingSelector: 'h1,h2,h3,h4,h5,h6',
        linkClass: 'tocbot-link',
        activeLinkClass: 'tocbot-active-link',
        listClass: 'tocbot-list',
        isCollapsedClass: 'tocbot-is-collapsed',
        collapsibleClass: 'tocbot-is-collapsible',
        collapseDepth: 0,
        scrollSmooth: true,
        headingsOffset: -boardTop
      });
      if ($('.toc-list-item').length > 0) {
        $('#toc').css('visibility', 'visible');
      }
    });
  </script>



  <script  src="https://cdn.staticfile.org/typed.js/2.0.11/typed.min.js" ></script>
  <script>
    var typed = new Typed('#subtitle', {
      strings: [
        '  ',
        "纯手写LRU算法！&nbsp;",
      ],
      cursorChar: "_",
      typeSpeed: 70,
      loop: false,
    });
    typed.stop();
    $(document).ready(function () {
      $(".typed-cursor").addClass("h2");
      typed.start();
    });
  </script>



  <script  src="https://cdn.staticfile.org/anchor-js/4.2.2/anchor.min.js" ></script>
  <script>
    anchors.options = {
      placement: "right",
      visible: "hover",
      
    };
    var el = "h1,h2,h3,h4,h5,h6".split(",");
    var res = [];
    for (item of el) {
      res.push(".markdown-body > " + item)
    }
    anchors.add(res.join(", "))
  </script>



  <script  src="/binblog/js/local-search.js" ></script>
  <script>
    var path = "/binblog/local-search.xml";
    var inputArea = document.querySelector("#local-search-input");
    inputArea.onclick = function () {
      searchFunc(path, 'local-search-input', 'local-search-result');
      this.onclick = null
    }
  </script>



  <script  src="https://cdn.staticfile.org/fancybox/3.5.7/jquery.fancybox.min.js" ></script>
  <link  rel="stylesheet" href="https://cdn.staticfile.org/fancybox/3.5.7/jquery.fancybox.min.css" />

  <script>
    $('#post img:not(.no-zoom img, img[no-zoom]), img[zoom]').each(
      function () {
        var element = document.createElement('a');
        $(element).attr('data-fancybox', 'images');
        $(element).attr('href', $(this).attr('src'));
        $(this).wrap(element);
      }
    );
  </script>





  

  
    <!-- MathJax -->
    <script>
      MathJax = {
        tex: {
          inlineMath: [['$', '$'], ['\\(', '\\)']]
        },
        options: {
          renderActions: {
            findScript: [10, doc => {
              document.querySelectorAll('script[type^="math/tex"]').forEach(node => {
                const display = !!node.type.match(/; *mode=display/);
                const math = new doc.options.MathItem(node.textContent, doc.inputJax[0], display);
                const text = document.createTextNode('');
                node.parentNode.replaceChild(text, node);
                math.start = { node: text, delim: '', n: 0 };
                math.end = { node: text, delim: '', n: 0 };
                doc.math.push(math);
              });
            }, '', false],
            insertedScript: [200, () => {
              document.querySelectorAll('mjx-container').forEach(node => {
                let target = node.parentNode;
                if (target.nodeName.toLowerCase() === 'li') {
                  target.parentNode.classList.add('has-jax');
                }
              });
            }, '', false]
          }
        }
      };
    </script>

    <script async src="https://cdn.staticfile.org/mathjax/3.0.5/es5/tex-svg.js" ></script>

  













  

  

  

  

  

  





<script src="/binblog/live2dw/lib/L2Dwidget.min.js?094cbace49a39548bed64abff5988b05"></script><script>L2Dwidget.init({"model":{"jsonPath":"/binblog/live2dw/assets/koharu.model.json"},"display":{"position":"right","width":150,"height":300},"mobile":{"show":true},"log":false,"pluginJsPath":"lib/","pluginModelPath":"assets/","pluginRootPath":"live2dw/","tagMode":false});</script></body>
</html>
